package Hot100;

import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author zhangmin
 * @create 2021-12-29 10:55
 */
public class longestConsecutive128 {

    /**
     * 128. 最长连续序列
     * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
     * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
     * 1、set记录有哪些数字出现，然后遍历每个元素，以i为起点，查找最长能有多长
     * */
    public int longestConsecutive(int[] nums) {
        int n=nums.length;
        if (n<=1) return n;
        int res=0;
        Set<Integer> set=new HashSet<>();
        for (int i = 0; i < n; i++) {
            set.add(nums[i]);
        }
        for (int num:nums) {
            if (!set.contains(num-1)){
                int curNum=num;
                int curStack=1;
                while (set.contains(curNum+1)){
                    curNum+=1;
                    curStack+=1;
                }
                res=Math.max(res,curStack);
            }
        }
        return res;
    }
}
